/*
 *    AgrawalSrikantSequenceGenerator.java
 *    Copyright (C) 2010 University of Waikato, Hamilton, New Zealand
 *    @author Celia Biguzzi, Albert Bifet
 *
 *    This program is free software; you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation; either version 2 of the License, or
 *    (at your option) any later version.
 *
 *    This program is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with this program; if not, write to the Free Software
 *    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

package moa.streams.generators;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;

import weka.core.Attribute;
import weka.core.FastVector;
import weka.core.Instance;
import weka.core.Instances;
import moa.core.InputStreamProgressMonitor;
import moa.core.InstancesHeader;
import moa.core.ObjectRepository;
import moa.core.MiscUtils;
import moa.options.AbstractOptionHandler;
import moa.options.FloatOption;
import moa.options.IntOption;
import moa.sequencestreams.generator.Transaction;
import moa.streams.InstanceStream;
import moa.streams.generators.AgrawalSrikantItemsetGenerator.Itemset;
import moa.streams.generators.AgrawalSrikantItemsetGenerator.tableItemsets;
import moa.tasks.TaskMonitor;

// Sequence Generator described in the paper:
//   Rakesh Agrawal, Ramakrishnan Srikant
//    "Fast Algorithms for Mining sequential patterns in Large Databases", 
//     VLDB '94: Proceedings of the 20th International Conference on Very Large Data Bases,
//      pages 487-499, 1994.
// Public C++ source code available at:
//   http://www.almaden.ibm.com/software/quest/Resources/datasets/syndata.html#assocSynDat
//


public class AgrawalSrikantSequenceGenerator extends AbstractOptionHandler implements InstanceStream {

	@Override
	public String getPurposeString() {
		return "Generates itemsets simulating transactions in a retailing environment.";
	}
		

			
	public FloatOption correlationLevelSeqOption = new FloatOption(
			"correlationLevelSeq", 'c',
			"Correlation Level.", .5);
	
	public FloatOption correlationLevelItOption = new FloatOption(
			"correlationLevelIt", 'b',
			"Correlation Level.", .5);
			
	public IntOption instanceRandomSeedOption = new IntOption(
			"instanceRandomSeed", 'i',
			"Seed for random generation of instances.", 1);		
	
	public IntOption averageNumberOfTransactionPerCustomerOption = new IntOption(
			"averageNumberOfTransactionPerCustomer", 't',
			"Number of transaction per customer", 10);		

	
	public FloatOption averageSizeMaximalPotentiallyLargeSequencesOption = new FloatOption(
			"averageSizeMaximalPotentiallyLargeSequences", 'l',
			"Average size of the maximal potentially large sequences.", 2.5);
	
	public FloatOption averageSizeTransactionOption = new FloatOption(
			"averageSizeTransaction", 's',
			"Average size of the transactions.", 1.25);
	
	public FloatOption averageSizeMaximalPotentiallyFrequentItemsetsOption = new FloatOption(
			"averageSizeMaximalPotentiallyFrequentItemsets", 'm',
			"Average size of the maximal potentially frequent itemsets.", 5);
	
	public IntOption numberOfMaximalPotentiallyLargeSequencesOption = new IntOption(
			"numberOfMaximalPotentiallyLargeSequences", 'q',
			"Number of maximal potentially large sequences", 5000);	
	
	public IntOption numberOfMaximalPotentiallyFrequentItemsetsOption = new IntOption(
			"numberOfMaximalPotentiallyFrequentItemsets", 'p',
			"Number of maximal potentially frequent itemsets", 25000);		
	
	public IntOption numberItemsOption = new IntOption(
			"numberItems", 'n',
			"Number of items.", 10000);
	
	protected InstancesHeader streamHeader;
	
	protected int numberItems;
	
	protected class Itemset{
		private List<Integer> itemSet;
		public Itemset(int item){
			add(item);
		}
		
		public Itemset(){
			itemSet = new ArrayList<Integer>(); 
		}

		public void add(int value){
			// Add no duplicates, in a sorted way
			int pos = Collections.binarySearch(this.itemSet, value);
    		if (pos < 0)
				this.itemSet.add(-pos-1, value);
		}
		
		public void addAll(Itemset is){
			this.itemSet.addAll(is.getItemset());
			Collections.sort(this.itemSet);
		}
		
		public List<Integer> getItemset(){
			return itemSet;
		}
		
		public int get(int index){
			return itemSet.get(index);
		}
		
		public void remove(int value){
			this.itemSet.remove(value);
		}
		
		
		
		public Itemset getRandomItems(int number, Random random){
			Itemset is = new Itemset();
			is.itemSet = new ArrayList<Integer>(this.itemSet);//this.itemSet.clone();

			//Delete items
			while ( is.size()> number) {
				is.remove(random.nextInt(is.size()));
			}
			return is;
		}
		
		public String toString(){
			StringBuffer r = new StringBuffer ();
			for(int attribute : itemSet){
				r.append(attribute);
				r.append(' ');
			}
			return r.toString();
		}

		public String StringAsASequence(){
			StringBuffer r = new StringBuffer ();
			for(int sequence : itemSet){
				Itemset itset = new Itemset();
				itset = tableMaximalPotentiallyFrequentItemsets.getItemset(sequence);
				r.append(itset.toString());
				r.append("-1 ");
			}
			return r.toString();			
		}
		
		public int size(){
			return this.itemSet.size();
		}
		
	}


	protected class tableItemsets {

			private Itemset[] itemsets;
		
			private double[] weight;
		
			private double[] sumWeight;
		
			private double[] corruptLevel;
		
			private int size;

			private double sum;
			
			public Itemset getItemset(int index){
				return this.itemsets[index];
			}

			public int getSize(){
				return this.size;
			}

			public double getWeight(int index){
				return this.weight[index];
			}

			public double getSumWeight(int index){
				return this.sumWeight[index];
			}

			public double getCorruptLevel(int index){
				return this.corruptLevel[index];
			}

			public tableItemsets(int sizeTable, double averageSizeItemset, double correlationLevel, int numberItems, Random streamRandom){
				this.size = sizeTable;
				this.itemsets = new Itemset[size];
				int fraction ;	
				// An itemset is generated by first picking the size of the
				// itemset from a Poisson distribution
				int sizeItemset = 1 + MiscUtils.poisson(averageSizeItemset - 1, streamRandom);

				// Items in the first itemset are chosen randomly		
				this.itemsets[0] = new Itemset();
				while (this.itemsets[0].size() < sizeItemset){
					this.itemsets[0].add(streamRandom.nextInt(numberItems));
				}
				
				for (int i = 1; i < this.size; i++){
						sizeItemset = 1 + MiscUtils.poisson(averageSizeItemset - 1, streamRandom);
						// Some fraction of items in subsequent itemsets are chosen from the previous itemset
						// An exponential distributed random variable with mean equal to the correlation level
						// is used to decide the fraction for each itemset
					
						fraction = (int) ( (double) sizeItemset * MiscUtils.exponentialDistribution(correlationLevel, streamRandom));
					
						if (fraction > sizeItemset) {
							 fraction  = sizeItemset;
						}
						
						// choose fraction items at random from previous pattern
						this.itemsets[i] = this.itemsets[i-1].getRandomItems(fraction, streamRandom);		
	
						// The remaining items are picked at random
						while (this.itemsets[i].size() < sizeItemset){
							// sometimes some items are repetition
							//if repetition == 0 Then 
							this.itemsets[i].add(streamRandom.nextInt(numberItems));
							//else
							// float rept_lvl = (float) rd.nextGaussian(rept, rept_var);
							// if ( j > 0 && rd.nextUniform(0, 1) < rept_lvl )	// pick a previous item
							//{
							//	pat[i].items[j] = pat[i].items[ (int)(j*rd.nextUniform(0, 1)) ];
							//}	
						}
				}
				//Each itemset has a weight associated with it, which corresponds to the probability
				//that this itemset will be picked. 
				this.weight = new double[this.size];
				this.sumWeight = new double[this.size];
			
				//This weight is picked from an exponential distribution with unit mean
				//double sum = 0;
				for (int i = 0; i < this.size; i++){
					this.weight[i] = MiscUtils.exponentialDistribution(1.0, streamRandom);
					sum += this.weight[i];
				}
				// It is then normalized. We compute a cumulative sum for speed purposes generating new instances.
				double cumulativeSum = 0;
				for (int i = 0; i < this.size; i++){
					this.weight[i] /= sum;
					cumulativeSum += this.weight[i];
					this.sumWeight[i] = cumulativeSum;
				}
			
				//Each itemset has a corruption level c. It is fixed and is obtained from a normal distribution with mean 0.5 and variance 0.1
				this.corruptLevel = new double[this.size];
				for (int i = 0; i < this.size; i++){
					this.corruptLevel[i] = MiscUtils.normalDistribution(0.5, 0.1, streamRandom);
				}

			}
		
  			protected int indexChangeItem = 0;

			public void replaceRow (double correlationLevel, double averageSizeItemset, int numberItems, Random streamRandom) 
			{
				// An itemset is generated by first picking the size of the
				// itemset from a Poisson distribution
				int sizeItemset = 1 + MiscUtils.poisson(averageSizeItemset - 1, streamRandom);

				if (indexChangeItem != 0)
				{	
					sizeItemset = 1 + MiscUtils.poisson(averageSizeItemset - 1, streamRandom);
	
					int fraction = (int) ( (double) sizeItemset * MiscUtils.exponentialDistribution(correlationLevel, streamRandom));
					
					if (fraction > sizeItemset) {
							 fraction  = sizeItemset;
					}
				
					this.itemsets[indexChangeItem] = this.itemsets[indexChangeItem-1 % this.size].getRandomItems(fraction, streamRandom);	//**	
	
					// The remaining items are picked at random
					while (this.itemsets[indexChangeItem].size() < sizeItemset){
						this.itemsets[indexChangeItem].add(streamRandom.nextInt(numberItems));
					}	
				}
				else
				{

						// Items in the first itemset are chosen randomly		
						this.itemsets[0] = new Itemset();
						while (this.itemsets[0].size() < sizeItemset){
							this.itemsets[0].add(streamRandom.nextInt(numberItems));
						}
				}

				double weightBefore  = this.weight[indexChangeItem];
				double cumulativeSumBefore = this.sumWeight[indexChangeItem];
			
				//This weight is picked from an exponential distribution with unit mean
				this.weight[indexChangeItem] = MiscUtils.exponentialDistribution(1.0, streamRandom);
				sum = sum - weightBefore + this.weight[indexChangeItem];
				
				// It is then normalized. We compute a cumulative sum for speed purposes generating new instances.
				double cumulativeSum = 0; 
				for (int i = 0; i < this.size; i++){ 
					this.weight[i] /= sum; 
					cumulativeSum += this.weight[i]; 
					this.sumWeight[i] = cumulativeSum; 
				}
			
				//Each itemset has a corruption level c. It is fixed and is obtained from a normal distribution with mean 0.5 and variance 0.1
				this.corruptLevel[indexChangeItem] = MiscUtils.normalDistribution(0.5, 0.1, streamRandom);
				
				indexChangeItem++; 
				if (indexChangeItem > getSize()) 
					indexChangeItem = 0;				

			}
			
			public void print() {
				//for (int i = 0; i < this.getSize(); i++)
				for (int i = 0; i < 20; i++) // Just to permit to see a little part
					System.out.println(i+"/ "+this.getItemset(i).toString());
			}

		}

	protected Random streamRandom; 
	
	
	protected tableItemsets tableMaximalPotentiallyFrequentItemsets;
	protected tableItemsets tableMaximalPotentiallyLargeSequences;
	


	private int numberOfMaximalPotentiallyLargeSequences;

	
	
	
	@Override
	protected void prepareForUseImpl(TaskMonitor monitor, ObjectRepository repository) {
        monitor.setCurrentActivity("Preparing random itemset values...", -1.0);
        restart();

        //Create a series of potentially frequent itemsets
        this.tableMaximalPotentiallyFrequentItemsets = new tableItemsets(
                (int) this.numberOfMaximalPotentiallyFrequentItemsetsOption.getValue(),
                (double) this.averageSizeMaximalPotentiallyFrequentItemsetsOption.getValue(),
                (double) this.correlationLevelItOption.getValue(),
                (int) this.numberItemsOption.getValue(),
                this.streamRandom);
        
        //this.tableMaximalPotentiallyFrequentItemsets.print();
I really eno
        //Create a series of potentially large sequences
        this.tableMaximalPotentiallyLargeSequences = new tableItemsets(
                (int) this.numberOfMaximalPotentiallyLargeSequencesOption.getValue(),
                (double) this.averageSizeMaximalPotentiallyLargeSequencesOption.getValue(),
                (double) this.correlationLevelSeqOption.getValue(),
                (int) this.tableMaximalPotentiallyFrequentItemsets.size , //(int) this.numberOfMaximalPotentiallyFrequentItemsetsOption.getValue(),
                this.streamRandom);
        
        //this.tableMaximalPotentiallyLargeSequences.print();

        generateHeader();
	}

	private void generateHeader() {
		FastVector attributes = new FastVector();
		Attribute atr = new Attribute("String", (FastVector) null);
		attributes.addElement(atr);
		this.streamHeader = new InstancesHeader(new Instances(
				getCLICreationString(InstanceStream.class), attributes, 0));
		this.streamHeader.setClassIndex(this.streamHeader.numAttributes() - 1);
	}

	public long estimatedRemainingInstances() {
		return -1;
	}

	public InstancesHeader getHeader() {
		return this.streamHeader;
	}

	public boolean hasMoreInstances() {
		return true;
	}

	public boolean isRestartable() {
		return true;
	}

    private boolean usePreviousChoosedSequence = false;
    private int PreviousChoosedSequence = 0; 
    public int chooseSequence(tableItemsets table){
		// Choose a sequence from the series of potentially large sequences
		if (this.usePreviousChoosedSequence == true) {
			// Use the large sequence that did not fit in the last transaction
			this.usePreviousChoosedSequence = false;
			return this.PreviousChoosedSequence;
		}
		// Sequence chosen by tossing a weighted coin,
	    // where the weight for a side is the probability of picking the associated sequence.
		double randomValue = MiscUtils.uniformDistribution(this.streamRandom);
		int i = 0;
		while (i==0){
			for (i = 0; i < table.getSize(); i++){
				if (table.getSumWeight(i) > randomValue) 
				  break;
			}
		}
		this.usePreviousChoosedSequence = false; // CHECK VALIDITY
		this.PreviousChoosedSequence = i-1;
		return i-1;
	}
    
	
    public boolean addSequence (int indexSequenceChoosed, int sizeSeq, int sizeItemset)
    {
    	int olditems;
    	// Get the ItemSet with a List of link to the tableMaximalPotentiallyFrequentItemsets values
		Itemset addSequence = this.tableMaximalPotentiallyLargeSequences.getItemset(indexSequenceChoosed);
		
    	int newitems ,i;
    	// calculate # of items in pattern (TO DO -- ADD SHUFFLE POSITION)
    	 for (newitems = 0, i = 0; i < addSequence.size(); i++)
    	 {	 
    	   newitems += 
    		   this.tableMaximalPotentiallyFrequentItemsets.getItemset(
    			   this.tableMaximalPotentiallyLargeSequences.getItemset(indexSequenceChoosed).get(i)).size();
    	 }  
    	
		// If the large sequence on hand does not fit in the transaction, the sequence is put
		// in the transaction anyway in half the cases, and the sequence is moved to
		// the next transaction the rest of the cases.

		if (addSequence.size()  > sizeSeq || (newitems + sizeItemNextSequence > sizeSeq * sizeItemset)) {
			if (MiscUtils.uniformDistribution(this.streamRandom) > 0.5) {
				this.usePreviousChoosedSequence = true;
				return false;
			}
		}
		
		// When adding a sequence to a transaction, we keep dropping an item from the sequence as long
		// as uniformly distributed random number between 0 and 1 is less than the corruption level for
		// this itemset.
		double c = this.tableMaximalPotentiallyLargeSequences.getCorruptLevel(indexSequenceChoosed);
			
		boolean dropping = true;
		for (int j = 0; j< addSequence.size(); j++) {
			if (dropping == true ) {
				if ( MiscUtils.uniformDistribution(this.streamRandom) >= c ){
						// with probability 1-c
					dropping = false;
				}
			} 
			if (dropping == false) {
				 // add new sequence
				if (nextSequence[j] == null)
				{	
					nextSequence[j] = new Itemset();
				}	
				olditems = nextSequence[j].size();
				//int itSet = this.tableMaximalPotentiallyLargeSequences.getItemset(indexSequenceChoosed).get(j);
				int itSet = this.tableMaximalPotentiallyLargeSequences.getItemset(indexSequenceChoosed).get(this.streamRandom.nextInt(addSequence.size()));
				Itemset addItemset = new Itemset();
				addItemset = this.addItemset(itSet,sizeItemset);
				if (addItemset != null) // TO DO : Test if the itemset is null
				{	
					nextSequence[j].addAll(addItemset); 
					sizeItemNextSequence += nextSequence[j].size() - olditems;
					sizeTransactionNextSequence ++;
				}
			} 					
		}
    	return true;
    }
    
    public Itemset addItemset(int indexItemsetChoosed,int sizeItemset)
    {
    	Itemset itemset = new Itemset();
		// If the large itemset on hand does not fit in the transaction, the itemset is put
		// in the transaction anyway in half the cases, and the itemset is moved to
		// the next transaction the rest of the cases.
		Itemset addItemset = this.tableMaximalPotentiallyFrequentItemsets.getItemset(indexItemsetChoosed);
		if (addItemset.size() + itemset.size() > sizeItemset) {
			if (MiscUtils.uniformDistribution(this.streamRandom) > 0.5) {
				return null;
			}
		}
						
		// When adding an itemset to a transaction, we keep dropping an item from the itemset as long
		// as uniformly distributed random number between 0 and 1 is less than the corruption level for
		// this itemset.
		double c = this.tableMaximalPotentiallyFrequentItemsets.getCorruptLevel(indexItemsetChoosed);
		
		boolean dropping = true;
		for (int j = 0; j< addItemset.size(); j++) {
			if (dropping == true ) {
				if ( MiscUtils.uniformDistribution(this.streamRandom) >= c ){
					// with probability 1-c
					dropping = false;
				}
			} 
			if (dropping == false) {
				itemset.add(addItemset.get(j));
			}
		} 
    	return itemset;
    }
    
    protected Itemset seq;
    protected Itemset[] nextSequence;
    protected int sizeTransactionNextSequence;
    protected int sizeItemNextSequence;
    
    protected int cptInstance = 0;
    
	@Override
	public Instance nextInstance() {
		cptInstance ++;
		InstancesHeader header = getHeader();
		Instance inst = new Instance(header.numAttributes());
		
		//Generate a customer sequence
		seq = new Itemset();
		
		int sizeSeq = MiscUtils.poisson(this.averageNumberOfTransactionPerCustomerOption.getValue(), this.streamRandom);
		int sizeItemset = 1 + MiscUtils.poisson(this.averageSizeTransactionOption.getValue() - 1, this.streamRandom);
		nextSequence = new Itemset[10 * sizeSeq];
		sizeTransactionNextSequence = 0;
		sizeItemNextSequence = 0;
		while (sizeTransactionNextSequence < sizeSeq){
			//The next sequence to be put in the the customer sequence is chosen by tossing a weighted coin,
			//where the weight for a side is the probability of picking the associated sequence.
			int indexSequenceChoosed = chooseSequence(this.tableMaximalPotentiallyLargeSequences);
			if (this.addSequence (indexSequenceChoosed,sizeSeq,sizeItemset) == false)
			{
				//lseq.unget_pat(); A REVOIR
		        break;
			}
				
		} 	
		String test = "";
		for (int k=0; k< nextSequence.length; k++)
		{
			if (nextSequence[k] != null)
				if (nextSequence[k].toString() != "" || nextSequence[k].toString() != " ")
				{	
					test = test + nextSequence[k].toString() + " -1 ";
				}	
		}
		
		inst.setDataset(header);
		inst.setValue(0, test );
		
		if (test == ""){
			return nextInstance();
		} else {
			return inst;
		}
	}
	
	public void restart() {
		this.streamRandom = new Random(this.instanceRandomSeedOption
				.getValue());
	}

	@Override
	public void getDescription(StringBuilder sb, int indent) {
		// TODO Auto-generated method stub
		
	}

}
